﻿#include "pch.h"
#include "CppUnitTest.h"
#include "../ForTest.h"

using namespace Microsoft::VisualStudio::CppUnitTestFramework;


namespace NCheck {
	typedef int rint;
	const int N = 1e5 + 5, M = 2e6 + 5;

	bool f[N];
	//f 在搜索中判断是否走过

	int n, m, mod, now, d[N], a[N], ans, maxans, ch[N];
	//d指从u到终点的最长链距离，a指最长链点数，ch指出度

	int h[N], u[M], v[M], r[N], nu[M], cnt;
	//h是链式前向星的建边head，u，v保存初始读入的边左右两点，nu存初始时边的编号，r是入度

	int top, co, dfn[N], low[N], c[N], s[N], st[N];
	//dfn，low，st用于Tarjan，c表所在强连通分量编号，s指所在强连通分量点数

	struct edge {
		int h, to;
	} e[M];

	inline bool cmp(int a, int b) {
		return u[a] < u[b] || (u[a] == u[b] && v[a] < v[b]);
	}//将边排序，方便重新建图

	inline void add(int u, int v) {
		e[++cnt].h = h[u], h[u] = cnt, e[cnt].to = v;
	}

	inline void Tarjan(int u) {
		dfn[u] = low[u] = ++now;
		st[++top] = u;
		for (rint i = h[u]; i; i = e[i].h) {
			int v = e[i].to;
			if (!dfn[v])
				Tarjan(v), low[u] = min(low[u], low[v]);
			else if (!c[v])
				low[u] = min(low[u], dfn[v]);
		}
		if (low[u] == dfn[u]) {
			c[u] = ++co, s[co]++;
			while (st[top] != u)
				s[co]++, c[st[top]] = co, top--;
			top--;
		}
	}//标准缩点

	inline void dfs(int u) {
		f[u] = 1;
		if (!ch[u]) {//如果没有出度，即到头了
			d[u] = s[u], a[u] = 1;//距离为点数，以u为起点方案为1
			maxans = max(maxans, d[u]);//更新最长链距离
			return;
		}
		for (rint i = h[u]; i; i = e[i].h) {
			int v = e[i].to;
			if (!f[v]) dfs(v);//继续搜索链的后面
			if (d[v] + s[u] > d[u])//若以u为起点的链距离可以更长
				d[u] = d[v] + s[u], a[u] = a[v] % mod;//更新
			else if (d[u] == d[v] + s[u])//若最长链距离相同
				a[u] = (a[u] + a[v]) % mod;//加上方案数
			maxans = max(maxans, d[u]);
		}
	}

	pair<int,int> main(const int iN, const vector<pair<int, int>>& edge,int Mod) {
		memset(e, 0, sizeof(e));
		memset(f, 0, sizeof(f));
		memset(a, 0, sizeof(a));
		memset(d, 0, sizeof(d));
		memset(ch, 0, sizeof(ch));

		memset(h, 0, sizeof(h));
		memset(u, 0, sizeof(u));
		memset(v, 0, sizeof(v));
		memset(r, 0, sizeof(r));
		memset(nu, 0, sizeof(nu));

		memset(dfn, 0, sizeof(dfn));
		memset(low, 0, sizeof(low));
		memset(c, 0, sizeof(c));
		memset(s, 0, sizeof(s));
		memset(st, 0, sizeof(st));

		now = ans = maxans = 0;
		cnt = top = co = 0;

		n= iN, m = edge.size(), mod = Mod;
		for (rint i = 1; i <= m; i++) u[i] = edge[i-1].first, v[i] = edge[i - 1].second, add(u[i], v[i]);
		for (rint i = 1; i <= n; i++) if (!dfn[i]) Tarjan(i);

		cnt = 0;
		memset(h, 0, sizeof h);
		memset(e, 0, sizeof e);
		for (rint i = 1; i <= m; i++)
			nu[i] = i, u[i] = c[u[i]], v[i] = c[v[i]];

		sort(nu + 1, nu + m + 1, cmp);//按u，v排序边
		for (rint i = 1; i <= m; i++)
		{
			int num = nu[i];
			if (u[num] != v[num] && (u[num] != u[nu[i - 1]] || v[num] != v[nu[i - 1]]))//若此边不是自环，且与上一条边不同（去除重边）
				++ch[u[num]], ++r[v[num]], add(u[num], v[num]);
		}
		//出度入度加1，加边
		for (rint i = 1; i <= co; i++) if (!r[i] && !f[i]) dfs(i);//入度为0且未搜索过
		for (rint i = 1; i <= co; i++) if (d[i] == maxans) ans = (ans + a[i]) % mod;//统计答案
		return make_pair( maxans, ans);
	}
}

namespace NSCC
{
	class CSCCTarjan {
	public:
		CSCCTarjan(vector<vector<int>>& neiBo) :m_neiBo(neiBo) {
			const int N = neiBo.size();
			m_vTime.assign(N, -1);
			m_vBack.assign(N, -1);
			m_vIsStack.assign(N, false);
			for (int i = 0; i < N; i++) {
				DFS(i);
			}
		}
		void InitPtNew() {
			m_ptNew.resize(m_neiBo.size());
			iota(m_ptNew.begin(), m_ptNew.end(), 0);
			for (auto& v : m_sccs) {
				nth_element(v.begin(), v.begin(), v.end());
				m_v0.emplace_back(v[0]);
				for (int i = 1; i < v.size(); i++) {
					m_ptNew[v[i]] = v[0];
				}
			}
		}
		vector<int> RingSize() {
			vector<int> ringSize(m_ptNew.size());
			for (const auto& i : m_ptNew) {
				ringSize[i]++;
			}
			return ringSize;
		}
		vector<vector<int>> GetNewNeiBo() {
			vector<vector<int>> neiBo(m_neiBo.size());
			for (int i = 0; i < neiBo.size(); i++) {
				const int n1 = m_ptNew[i];	
				for (const auto& next : m_neiBo[i]) {
					const int n2 = m_ptNew[next];
					if (n1 == n2) { continue; }//自环
					neiBo[n1].emplace_back(n2);
				}
			}
			for (int i = 0; i < neiBo.size(); i++) {
				unordered_set<int> s(neiBo[i].begin(),neiBo[i].end());
				vector<int> tmp(s.begin(), s.end());
				neiBo[i].swap(tmp);
			}
			return neiBo;
		}
		vector<vector<int>> m_sccs;
		vector<int> m_v0, m_ptNew;
	protected:
		void DFS(int cur) {
			if (-1 != m_vTime[cur]) { return; }
			m_vTime[cur] = m_vBack[cur] = m_iTimes++;
			m_vIsStack[cur] = true;
			m_sta.emplace(cur);
			for (const auto& next : m_neiBo[cur]) {
				if (-1 == m_vTime[next]) {
					DFS(next);
					m_vBack[cur] = min(m_vBack[cur], m_vBack[next]);
				}
				else if (m_vIsStack[next]) {
					m_vBack[cur] = min(m_vBack[cur], m_vTime[next]);
				}
			}
			if (m_vTime[cur] != m_vBack[cur]) { return; }
			vector<int> scc;
			while (m_sta.size())
			{
				auto u = m_sta.top(); m_sta.pop();
				scc.emplace_back(u);
				m_vIsStack[u] = false;
				if (cur == u) { break; }
			}
			m_sccs.emplace_back(scc);
		}		
		vector<vector<int>>& m_neiBo;
		int  m_iTimes = 0;
		vector<int> m_vTime, m_vBack;
		vector<bool> m_vIsStack;
		stack<int> m_sta;
	};
	class CSCCTarjanForwardStar {
	public:
		CSCCTarjanForwardStar(const int N, vector<pair<int, int>>& sortEdge) :m_sortEdge(sortEdge), RegionCnt(m_iRegionCnt){
			m_beginEnd.assign(N, { -1,-2 });
			for (int i = 0; i < sortEdge.size(); i++) {
				const int u = sortEdge[i].first;
				if (-1 == m_beginEnd[u].first) { m_beginEnd[u].first = i; }
				m_beginEnd[u].second = i;
			}
			m_vTime.assign(N, -1);
			m_vBack.assign(N, -1);
			m_ptNew.assign(N, -1);
			m_vIsStack.assign(N, false);
			for (int i = 0; i < N; i++) {
				DFS(i);
			}
		}
		vector<int> m_ptNew;
		const int& RegionCnt = 0;
	protected:
		void DFS(int cur) {
			if (-1 != m_vTime[cur]) { return; }
			m_vTime[cur] = m_vBack[cur] = m_iTimes++;
			m_vIsStack[cur] = true;
			m_sta.emplace(cur);
			for (int i = m_beginEnd[cur].first; i <= m_beginEnd[cur].second; i++) {
				const int next = m_sortEdge[i].second;
				if (-1 == m_vTime[next]) {
					DFS(next);
					m_vBack[cur] = min(m_vBack[cur], m_vBack[next]);
				}
				else if (m_vIsStack[next]) {
					m_vBack[cur] = min(m_vBack[cur], m_vTime[next]);
				}
			}
			if (m_vTime[cur] != m_vBack[cur]) { return; }
			m_iRegionCnt++;
			while (m_sta.size())
			{
				auto u = m_sta.top(); m_sta.pop();
				m_ptNew[u] = m_iRegionCnt -1;
				m_vIsStack[u] = false;
				if (cur == u) { break; }
			}
		}
		int m_iRegionCnt = 0;
		vector<pair<int, int>> m_beginEnd;
		int  m_iTimes = 0;
		vector<int> m_vTime, m_vBack;
		vector<bool> m_vIsStack;
		stack<int> m_sta;
		vector<pair<int, int>>& m_sortEdge;
	};
	TEST_CLASS(TestSCCTarjan)
	{		
	public:		
		TestSCCTarjan() {
			
		}
		void Test(const int N,const vector<pair<int, int>>& edge) {
			vector<vector<int>> neiBo(N);
			CFloyd<> floyd(N);
			wstring str = L"edge={";
			for (const auto& [u, v] : edge) {
				floyd.SetEdge(u, v, 0,true);
				neiBo[u].emplace_back(v);
				str += L"{" + to_wstring(u) + L"," + to_wstring(v) + L"},";
			}
			auto dis = floyd.Dis();
			str += L"};";
			CSCCTarjan scc(neiBo);
			scc.InitPtNew();
			vector<int> pt(N);
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if ((0 == dis[i][j]) && (0 == dis[j][i])) {
						pt[i] = j; break;
					}
				}
			}
			for (int i = 0; i < pt.size(); i++)
			{
				Assert::AreEqual(pt[i], scc.m_ptNew[i], str.c_str());
			}
		}
		TEST_METHOD(TestMethod01)
		{
			int N = 4;
			vector<pair<int, int>> edge = { {1,2},{2,1},{1,2},{3,2},{1,0},{3,3},{3,3},{3,0},{0,2},{2,1},{0,3} };
			Test(N, edge);
		}
		TEST_METHOD(TestMethod02)
		{
			int N = 4;
			CreateRandEdge cre;
			for(int i = 0;i < 2000;i++){ Test(N,cre.CreateTwo(N)); }			
		}	
		TEST_METHOD(TestMethod03)
		{
			int N = 10;
			CreateRandEdge cre;
			for (int i = 0; i < 20; i++) { Test(N, cre.CreateTwo(N)); }
		}
	};
	TEST_CLASS(P1262)
	{
		//【缩点 强连通分量】P1262 间谍网络|普及+
		
		class Solution {
		public:
			pair<bool,int> Ans(const int N, vector<pair<int, int>>& vNoMoney, vector<pair<int, int>>& edge) {
				vector<int> need(N, INT_MAX / 2);
				for (const auto& [v, Mon] : vNoMoney) {
					need[v - 1] = Mon;
				}
				auto neiBo = CNeiBo::Two(N, edge, true, 1);
				CSCCTarjan sp(neiBo);
				vector<vector<int>>& sccs = sp.m_sccs;
				vector<int> ptNew(N);
				iota(ptNew.begin(), ptNew.end(), 0);
				vector<int> v0;
				for (auto& v : sccs ) {
					nth_element(v.begin(), v.begin(), v.end());
					v0.emplace_back(v[0]);
					for (int i = 1; i < v.size(); i++) {
						need[v[0]] = min(need[v[0]], need[v[i]]);
						ptNew[v[i]] = v[0];
					}					
				}	
				sort(v0.begin(), v0.end());
				vector<int> in(N);
				vector<vector<int>> neiBo1(N);
				for (int i = 0; i < N; i++) {
					const int p1 = ptNew[i];
					for (const auto& next : neiBo[i]) {
						const int p2 = ptNew[next];
						if (p1 == p2) { continue; }//忽略自环
						in[p2]++;
						neiBo1[p1].emplace_back(p2);
					}
				}		
				
				int ans = 0;
				bool bCanAll = true;
				for (auto& n:v0) {
					if (0 != in[n]) { continue; }
					if (need[n] >= INT_MAX / 2) { bCanAll = false; break; }
					ans += need[n];	
				}
				if (bCanAll) {
					return { true,ans };
				}
				vector<int> can;
				for (auto& n : v0) {					
					if (need[n] >= INT_MAX / 2) { continue; }	
					can.emplace_back(n);
				}
				auto leves = CBFSLeve::Leve(neiBo1, can);
				int iMin = INT_MAX / 2;
				for (const auto& n : v0) {
					if (-1 == leves[n]) { return { false,n + 1 }; }
				}
				return { true,-1 };
			}
		};
	public:
		 int N;
		vector<pair<int, int>> noMoney, edge;
		TEST_METHOD(TestMethod01)
		{
			N = 3, noMoney = { {1,10},{2,100} }, edge = { {1,3},{2,3} };
			auto res = Solution().Ans(N, noMoney,edge);
			AssertEx({true,110 }, res);
		}
		TEST_METHOD(TestMethod02)
		{
			N = 4, noMoney = { {1,100},{4,200} }, edge = { {1,2},{3,4} };
			auto res = Solution().Ans(N, noMoney, edge);
			AssertEx({ false,3 }, res);
		}
		TEST_METHOD(TestMethod03)
		{
			N = 4, noMoney = { {1,2},{2,2} ,{3,3},{4,4} }, edge = { {1,2},{1,3},{1,4},{4,3},{3,2},{2,1} };
			auto res = Solution().Ans(N, noMoney, edge);
			AssertEx({ true,2 }, res);
		}
		TEST_METHOD(TestMethod05)
		{
			N = 9, noMoney = { {1,100},{9,10000} }, edge = { {1,3},{4,3},{2,4},{2,1},{8,5},{8,7},{5,6},{7,6},{4,5} };
			auto res = Solution().Ans(N, noMoney, edge);
			AssertEx({ false,2 }, res);
		}
		TEST_METHOD(TestMethod06)
		{
			N = 4, noMoney = { {4,10} }, edge = { {3,2},{3,1} };
			auto res = Solution().Ans(N, noMoney, edge);
			AssertEx({ false,1 }, res);
		}
	};
	TEST_CLASS(P1653)
	{
		//P1653 [USACO04DEC] Cow Ski Area G|普及+
		class Solution {
		public:
			int Ans(vector<vector<int>>& grid) {
				const int R = grid.size(),  C = grid[0].size();
				const int RC = R * C;
				vector<vector<int>> neiBo(RC);
				auto Add = [&](int r, int c, int r1, int c1) {
					if (grid[r][c] >= grid[r1][c1]) {
						neiBo[r * C + c].emplace_back(r1*C+c1);
					}
					if (grid[r1][c1] >= grid[r][c]) {
						neiBo[r1 * C + c1].emplace_back(r * C + c);
					}
				};
				for (int r = 0; r < R; r++) {
					for (int c = 0; c < C; c++) {
						if (r + 1 < R) {
							Add(r, c, r + 1, c);
						}
						if (c + 1 < C) {
							Add(r, c, r, c + 1);
						}
					}
				}
				CSCCTarjan scc(neiBo);
				if (scc.m_sccs.size() == 1) { return 0; }
				scc.InitPtNew();
				auto neiBo1 = scc.GetNewNeiBo();
				vector<int> in(RC), out(RC);
				for (int i = 0; i < RC;i++) {					
					for (const auto& j : neiBo1[i]) {
						out[i] ++; in[j]++;
					}
				}
				int in0=0, out0=0;
				for (const auto& i : scc.m_v0) {
					in0 += (0 == in[i]);
					out0 += (0 == out[i]);
				}
				return max(in0,out0);
			}
		};
	public:
		vector<vector<int>> grid;
		TEST_METHOD(TestMethod01)
		{
			grid = { {1,1,1,2,2,2,1,1,1},{1,2,1,2,3,2,1,2,1},{1,1,1,2,2,2,1,1,1} };
			auto res = Solution().Ans(grid);
			AssertEx(3, res);
		}
	};
	TEST_CLASS(P3387)
	{
		//【强连通分量 缩点 拓扑排序】P3387 【模板】缩点|普及+

		class Solution {
		public:
			int Ans(vector<int>& ws,vector<pair<int,int>>& edge) {
				const int N = ws.size();
				auto neiBo = CNeiBo::Two(N, edge, true, 1);
				CSCCTarjan scc(neiBo);
				scc.InitPtNew();
				for (auto& v : scc.m_sccs) {
					for (int i = 1; i < v.size(); i++) {
						ws[v[0]] += ws[v[i]];
					}
				}
				auto neiBo1 = scc.GetNewNeiBo();
				CDGTopSort ts(neiBo1);
				ts.Init();
				vector<int> ans = ws;
				for (const auto& cur : ts.m_vSort) {
					for (const auto& child : neiBo1[cur])
					{
						ans[cur] = max(ans[cur], ans[child] + ws[cur]);
					}
				}
				const int iMax = *max_element(ans.begin(), ans.end());
				return iMax;
			}
		};
	public:
		vector<int> ws;
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod01)
		{
			ws = { 1,1 }, edge = { {1,2},{2,1} };
			auto res = Solution().Ans(ws,edge);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod02)
		{
			ws = { 970,369,910,889,470,106,658,659,916,964 }, edge = { {3,2},{3,6},{3,4},{9,5},{8,3
},{5,8},{9,1},{9,7},{9,8},{7,5},{3,7},{7,8},{1,7},{10,2},{1,10},{4,8},{2,6},{3,1},{3,5},{8,5} };
			auto res = Solution().Ans(ws, edge);
			AssertEx(6911, res);
		}
	};
	TEST_CLASS(P2341)
	{
		//【强连通分量 缩点】P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G|普及+
		class Solution {
		public:
			int Ans(const int N , vector<pair<int, int>>& edge) {
				auto neiBo = CNeiBo::Two(N, edge, true, 1);
				CSCCTarjan scc(neiBo);
				scc.InitPtNew();
				if (1 == scc.m_sccs.size()) { return N; }
				auto neiBo1 = scc.GetNewNeiBo();
				vector<int> out(N);
				for (int i = 0; i < N;i++) {
					out[i] = neiBo1[i].size();
				}
				vector<int> out0;
				for (int i = 0; i < scc.m_v0.size();i++) {
					if (0==out[scc.m_v0[i]]) {
						out0.emplace_back(i);
					}					
				}
				if (1 == out0.size()) {
					return scc.m_sccs[out0[0]].size();
				}
				return 0;
			}
		};
	public:
		int N;
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod01)
		{
			N = 3, edge = { {1,2},{2,1},{2,3} };
			auto res = Solution().Ans(N, edge);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod02)
		{
			N = 3, edge = { {1,2},{3,1},{2,3} };
			auto res = Solution().Ans(N, edge);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod03)
		{
			N = 3, edge = { {1,2},{1,3} };
			auto res = Solution().Ans(N, edge);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod04)
		{
			N = 3, edge = { {1,3},{2,3} };
			auto res = Solution().Ans(N, edge);
			AssertEx(1, res);
		}
	};

	TEST_CLASS(P2656)
	{
		//【强连通分量 缩点 最长路 拓扑排序】P2656 采蘑菇|普及+
		class Solution {
		public:
			int Ans(const int N, vector<tuple<int, int, int, double>>& edge, int S) {
				S--;
				vector<vector<int>> neiBo(N);
				for (auto& [u, v, w, d] : edge) {
					u--, v--;
					neiBo[u].emplace_back(v);
				}
				CSCCTarjan scc(neiBo);
				scc.InitPtNew();
				vector<int> pw(N);
				vector < vector<pair<int, int>>> neiBo1(N);
				for (auto& [u, v, w, d] : edge) {
					const int i = scc.m_ptNew[u];
					const int j = scc.m_ptNew[v];
					if (i == j) {
						pw[i] += F(w, d);
					}
					else {
						neiBo1[i].emplace_back(j, w);
					}
				}
				CDGTopSort topSort(scc.GetNewNeiBo());
				topSort.Init();
				vector<int> ans = pw;
				for (const auto& cur : topSort.m_vSort) {
					for (const auto& [child, w] : neiBo1[cur]) {
						ans[cur] = max(ans[cur], ans[child] + w + pw[cur]);
					}
				}				
				return ans[scc.m_ptNew[S]];
			}
			int F(long long iInit, double d) {
				long long ret = 0;
				int p = d * 10;
				while (iInit) {
					ret += iInit;
					iInit = iInit * p / 10;
				}
				return ret;
			}
		};
	public:
		int N,S;
		vector<tuple<int, int, int, double>> edge;
		TEST_METHOD(TestMethod01)
		{
			N = 3, S = 1, edge = { {1,2,4,0.5},{1,3,7,0.1},{2,3,4,0.6} };
			auto res = Solution().Ans(N, edge,S);
			AssertEx(8, res);
		}
		TEST_METHOD(TestMethod02)
		{
			N = 3, S = 1, edge = { {1,2,4,0.5},{2,1,4,0.5},{2,3,4,0.6} };
			auto res = Solution().Ans(N, edge, S);
			AssertEx(18, res);
		}
		TEST_METHOD(TestMethod03)
		{
			N = 3, S = 1, edge = { {1,2,4,0.5},{2,1,4,0.5} };
			auto res = Solution().Ans(N, edge, S);
			AssertEx(14, res);
		}
		TEST_METHOD(TestMethod04)
		{
			N = 3, S = 2, edge = { {1,2,4,0.5},{2,1,4,0.5} };
			auto res = Solution().Ans(N, edge, S);
			AssertEx(14, res);
		}
	};

	TEST_CLASS(P4645)
	{
		//【强连通分量 拓扑序 分层图】 P4645 [COCI 2006/2007 #3] BICIKLI|普及+
		class Solution {
		public:
			int Ans(const int N, vector<pair<int,int>>& edge) {
				for (auto& [u, v] : edge) { u--, v--; }
				auto neiBo = CNeiBo::Two(N, edge, true, 0);
				CSCCTarjan scc(neiBo);
				scc.InitPtNew();
				vector<bool> bRing(N);
				for (auto& v : scc.m_sccs) {
					for (const auto& i : v) {
						bRing[i] = v.size() > 1;
					}
				}
				vector<vector<int>> leveNeiBo(2 * N);
				vector<vector<int>> neiBo2(N);
				for (const auto& [u, v] : edge) {
					const int i = scc.m_ptNew[u];
					const int j = scc.m_ptNew[v];
					if (i == j) { continue; }
					neiBo2[i].emplace_back(j);
					leveNeiBo[i].emplace_back(j);
					leveNeiBo[i+N].emplace_back(j+N);
					if (bRing[i]||bRing[j]) {
						leveNeiBo[i].emplace_back(j + N);
					}				
				}
				auto leves = CBFSLeve::Leve(leveNeiBo, { 0 });
				if (-1 != leves[1+N]) { return -1; }
				
				vector<C1097Int<1'000'000'000>> cnt(N);
				CDGTopSort topSort(neiBo2);
				topSort.Init();
				assert(topSort.m_vSort.size() == N);				
				for (const auto& cur : topSort.m_vSort) {
					if (1 == cur) { cnt[cur] = 1; continue; }
					for (const auto& child : neiBo2[cur]) {
						cnt[cur] += cnt[child];
					}
				}
				return cnt[0].ToInt();
			}
		};
	public:
		int N;
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod01)
		{
			N = 6, edge = { {1,3},{1,4},{3,2},{4,2},{5,6},{6,5},{3,4} };
			auto res = Solution().Ans(N, edge);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod02)
		{
			N = 6, edge = { {1,3},{1,4},{3,2},{4,2},{5,6},{6,5},{3,4},{4,3} };
			auto res = Solution().Ans(N, edge);
			AssertEx(-1, res);
		}
		TEST_METHOD(TestMethod03)
		{
			N = 4, edge = { {1,3},{1,4},{3,2},{4,2} };
			auto res = Solution().Ans(N, edge);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod04)
		{
			N = 5, edge = { {1,2},{1,3},{3,2} };
			auto res = Solution().Ans(N, edge);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod06)
		{
			N = 5, edge = { {1,2},{1,3},{3,2},{1,4},{3,4},{4,2} };
			auto res = Solution().Ans(N, edge);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod07)
		{
			N = 5, edge = { {1,2},{1,2} };
			auto res = Solution().Ans(N, edge);
			AssertEx(2, res);
		}
	};

	TEST_CLASS(P9431)
	{
		//【强连通分量 拓扑序】P9431 [NAPC-#1] Stage3 - Jump Refreshers|普及+
		class Solution {
		public:
			int Ans(const int D,int C, vector<pair<int, int>>& xy) {
				const int N = xy.size();
				vector<vector<int>> neiBo(N);
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						if (abs(xy[i].first - xy[j].first) + abs(xy[j].second ) <= xy[i].second + D) {
							neiBo[i].emplace_back(j);
						}
					}
				}
				CSCCTarjan scc(neiBo);
				scc.InitPtNew();
				vector<int> pw(N);
				for (const auto& v : scc.m_sccs) {
					for (const auto& i : v) {
						pw[i] = v.size();
					}
				}
				vector<int> ans = pw;
				auto neiBo2 = scc.GetNewNeiBo();
				CDGTopSort topSort(neiBo2);
				topSort.Init();
				for (const auto& cur : topSort.m_vSort) {
					for (const auto& child : neiBo2[cur]) {
						ans[cur] =max(ans[cur],ans[child]+pw[cur]);
					}
				}				
				return ans[scc.m_ptNew[C-1]];
			}
		};
	public:
		int D,C;
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod01)
		{
			D = 2, C = 1, edge = { {2,4},{1,1},{5,2},{4,1} };
			auto res = Solution().Ans(D,C, edge);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod02)
		{
			D = 3, C = 4, edge = { {1,7},{2,4},{3,2},{4,5},{8,2} };
			auto res = Solution().Ans(D, C, edge);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod03)
		{
			D = 1, C = 2, edge = { {1,1},{1,2},{1,3},{4,1} };
			auto res = Solution().Ans(D, C, edge);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod04)
		{
			D = 2, C = 1, edge = { {1,1},{4,1},{1,4},{4,4} };
			auto res = Solution().Ans(D, C, edge);
			AssertEx(1, res);
		}
	};

	TEST_CLASS(P2272)
	{
		//【拓扑排序 缩点】P2272 [ZJOI2007] 最大半连通子图|省选-
		class Solution {
		public:
			pair<int, int> Ans(const int N, const int MOD, vector<pair<int, int>>& edge) {
				for (auto& [u, v] : edge) { u--, v--; }
				auto neiBo1 = CNeiBo::Two(N, edge, true, 0);
				CSCCTarjan scc(neiBo1);
				scc.InitPtNew();
				m_pt = scc.m_ptNew;
				auto neiBo = scc.GetNewNeiBo();
				vector<int> ws(N);
				for (int i = 0; i < N; i++) {
					ws[scc.m_ptNew[i]] ++;
				}			
				vector<pair<int, int>> ans(N);
				for (int cur = 0; cur < N; cur++) {
					ans[cur] = make_pair(-1, 1);		
				}
				function<void(int)>DFS = [&](int cur) {
					if (-1 != ans[cur].first) { return; }
					ans[cur].first = ws[cur];
					for (const auto& next : neiBo[cur]) {	
						DFS(next);
						const int iNew = ans[next].first + ws[cur];
						if (iNew > ans[cur].first) {
							ans[cur] = { iNew,ans[next].second };
						}
						else if (iNew == ans[cur].first) {
							ans[cur].second = (ans[cur].second + ans[next].second) % MOD;
						}
					}
				};
				for (int i = 0; i < N; i++) {
					DFS(i);
				}
				int iMax = 1;
				for (int i = 0; i < N; i++) {
					iMax = max(iMax, ans[i].first);
				}
				int cnt = 0;
				for (int i = 0; i < N; i++) {
					if (ans[i].first == iMax) {
						cnt = (cnt + ans[i].second) % MOD;
					}
				}
				return { iMax,cnt };
			}
			vector<int> m_vTopSort,m_pt;
		};
	public:		
		int N, MOD=1024;
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod11)
		{
			N = 6,MOD = 20070603, edge = { {1,2},{2,1},{1,3},{2,4},{5,6},{6,4} };
			auto res = Solution().Ans(N, MOD, edge);
			AssertEx({ 3,3 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			N = 3, MOD = 20070603, edge = { {1,2},{2,1},{3,1} };
			auto res = Solution().Ans(N, MOD, edge);
			AssertEx({ 3,1 }, res);
		}
		TEST_METHOD(TestMethod13)
		{
			N = 4, MOD = 20070603, edge = { {1,2},{2,3},{3,4} };
			auto res = Solution().Ans(N, MOD, edge);
			AssertEx({ 4,1 }, res);
		}
		TEST_METHOD(TestMethod14)
		{
			N = 4, MOD = 20070603, edge = { {1,2},{2,1},{3,4},{4,3},{1,3},{2,3} };
			auto res = Solution().Ans(N, MOD, edge);
			AssertEx({ 4,1 }, res);
		}
		TEST_METHOD(TestMethod15)
		{
			N = 3, MOD = 20070603, edge = { {1,3},{2,3} };
			auto res = Solution().Ans(N, MOD, edge);
			AssertEx({ 2,2 }, res);
		}
		TEST_METHOD(TestMethod16)
		{
			N = 1'000, MOD = 100'000'000;
			for (int i = 1; i < N/2; i++) {
				edge.emplace_back(2 * i - 1, 2 * i + 1);
				edge.emplace_back(2 * i - 1, 2 * i + 2);
				edge.emplace_back(2 * i, 2 * i + 1);
				edge.emplace_back(2 * i, 2 * i + 2);
			}
			auto res = Solution().Ans(N, MOD, edge);
			int cnt = 1;
			for (int i = 1; i <= N / 2; i++) {
				cnt = (cnt + cnt) % MOD;
			}
			AssertEx({ N/2,cnt }, res);
		}
		TEST_METHOD(TestMethod17)
		{
			N = 3, MOD = 20070603, edge = { {1,3},{1,2} };
			auto res = Solution().Ans(N, MOD, edge);
			AssertEx({ 2,2 }, res);
		}
		TEST_METHOD(TestMethod18)
		{
			N = 3, MOD = 20070603, edge = { {1,3} };
			auto res = Solution().Ans(N, MOD, edge);
			AssertEx({ 2,1 }, res);
		}
		TEST_METHOD(TestMethod19)
		{
			N = 3, MOD = 20070603, edge = {  };
			auto res = Solution().Ans(N, MOD, edge);
			AssertEx({ 1,3 }, res);
		}
		TEST_METHOD(TestMethod20)
		{
			N = 3, MOD = 20070603, edge = { {1,2},{2,1} };
			auto res = Solution().Ans(N, MOD, edge);
			AssertEx({ 2,1 }, res);
		}
		TEST_METHOD(TestMethod21)
		{
			N = 3, MOD = 20070603, edge = { {1,2},{1,1},{2,2},{3,3} };
			auto res = Solution().Ans(N, MOD, edge);
			AssertEx({ 2,1 }, res);
		}
		TEST_METHOD(TestMethod22)
		{
			N = 3, MOD = 20070603, edge = { {1,2},{1,1},{2,2},{3,3} };
			Test(N, edge, MOD);
		}
		TEST_METHOD(TestMethod23)
		{
			N = 3, MOD = 1024, edge = { {1,2},{3,2},{2,1},{1,1} };
			Test(N, edge, MOD);
		}
		void Test(int N,  vector<pair<int, int>>& edge,int MOD) {
			auto str = CreateRandEdge::ToString(edge);
			auto eres = NCheck::main(N, edge, MOD);
			auto ares = Solution().Ans(N, MOD, edge);			
			Assert::AreEqual(eres.first, ares.first, (L"节点数"+str).c_str());
			Assert::AreEqual(eres.second, ares.second, (L"方案数" +str).c_str());
		}
		TEST_METHOD(TestMethod24)
		{			
			N = 10,MOD = 1234567;
			CreateRandEdge cre;
			for (int i = 0; i < 1*1000; i++)
			{
				auto edge = cre.CreateTwo(N,1);
				Test(N, edge, MOD);
			}
		}
	};

	TEST_CLASS(P2403)
	{
		//【拓扑排序】P2403 [SDOI2010] 所驼门王的宝藏|省选-
		class Solution {
		public:
			int Ans(const int R, const int C, vector<tuple<int, int, int>>& edge) {
				const int N = edge.size();
				vector<int> pw(N);
				vector<vector<int>> neiBo;
				{
					map<pair<int, int>, int> mCode;
					vector<vector<int>> rs(R + 1), rrooms(R + 1), cs(C + 1), crooms(C + 1);
					vector<pair<int, int>> edge3;
					for (const auto& [r, c, kind] : edge) {
						const int iCode = mCode.size();
						mCode[make_pair(r, c)] = iCode;
						rs[r].emplace_back(iCode);
						cs[c].emplace_back(iCode);
						if (1 == kind) {
							rrooms[r].emplace_back(iCode);
						}
						else if (2 == kind) {
							crooms[c].emplace_back(iCode);
						}
						else {
							edge3.emplace_back(r, c);
						}
					}
					vector<vector<int>> neiBo1(N);
					for (int r = 1; r <= R; r++) {
						if (0 == rrooms[r].size()) { continue; }
						for (int j = 1; j < rrooms[r].size(); j++) {
							neiBo1[rrooms[r][0]].emplace_back(rrooms[r][j]);
							neiBo1[rrooms[r][j]].emplace_back(rrooms[r][0]);
						}
						for (auto& code : rs[r]) {
							neiBo1[rrooms[r][0]].emplace_back(code);
						}
					}
					for (int c = 1; c <= C; c++) {
						if (0 == crooms[c].size()) { continue; }
						for (int j = 1; j < crooms[c].size(); j++) {
							neiBo1[crooms[c][0]].emplace_back(crooms[c][j]);
							neiBo1[crooms[c][j]].emplace_back(crooms[c][0]);
						}
						for (const auto& code : cs[c]) {
							neiBo1[crooms[c][0]].emplace_back(code);
						}
					}
					for (const auto& [r, c] : edge3) {
						for (int r1 = r - 1; r1 <= r + 1; r1++) {
							for (int c1 = c - 1; c1 <= c + 1; c1++) {
								if ((r == r1) && (c == c1)) { continue; }
								if (0 == mCode.count(make_pair(r1, c1))) { continue; }
								neiBo1[mCode[make_pair(r, c)]].emplace_back(mCode[make_pair(r1, c1)]);
							}
						}
					}
					CSCCTarjan scc(neiBo1);
					scc.InitPtNew();					
					for (const auto& v : scc.m_sccs) {
						for (const auto& i : v) {
							pw[i] = v.size();
						}
					}
					neiBo = scc.GetNewNeiBo();
					assert(mCode.size() == N);
				}
				vector<int> ans(N,-1);
				function<void(int)>DFS = [&](int cur) {
					if (-1 != ans[cur]) { return; }
					ans[cur] = pw[cur];
					for (const auto& next : neiBo[cur]) {
						DFS(next);
						ans[cur] = max(ans[cur], ans[next] + pw[cur]);
					}
				};
				for (int i = 0; i < N; i++) {
					DFS(i);
				}				
				return *max_element(ans.begin(),ans.end());
			}
		};
	public:
		int R,C;
		vector<tuple<int, int,int>> edge;
		TEST_METHOD(TestMethod01)
		{
			R = 7, C = 7, edge = { {2,2,1},{2,4,2},{1,7,2},{2,7,3},{4,2,2},{4,4,1},{6,7,3},{7,7,1},{7,5,2},{5,2,1} };
			auto res = Solution().Ans(R, C, edge);
			AssertEx(9, res);
		}
	};

	TEST_CLASS(P3119)
	{
		//【缩点 拓扑序】P3119 [USACO15JAN] Grass Cownoisseur G|省选-
		class Solution {
		public:
			int Ans(const int N, vector<pair<int, int>>& edge) {
				for (auto& [u, v] : edge) { u--, v--; }
				auto neiBo = CNeiBo::Two(N, edge, true, 0);
				CSCCTarjan scc(neiBo);
				scc.InitPtNew();
				m_ringSize.assign(N, 0);
				for (int i = 0; i < N; i++) {
					m_ringSize[scc.m_ptNew[i]]++;
				}
				auto neiBo1 = scc.GetNewNeiBo();
				vector<vector<int>> neiBo2(N);
				for (int i = 0; i < N; i++) {
					for (const auto& j : neiBo1[i]) {
						neiBo2[j].emplace_back(i);
					}
				}
				assert(0==scc.m_ptNew[0]);
				auto dis1 = More(N, neiBo1);
				auto dis2 = More(N, neiBo2);
				int ans = dis1[0];
				for (int u = 0; u < N; u++) {
					for (const auto& v : neiBo1[u]) {
						if ((0 == dis1[v]) || (0 == dis2[u])) { continue; }	
						if ((0 == scc.m_ptNew[u]) && (0 == scc.m_ptNew[v])) { continue; }
						ans = max(ans, dis1[v] + dis2[u]- m_ringSize[0]);
					}
				}
				return ans;
			}
			vector<int> More(const int N, vector<vector<int>>& neiBo) {
				vector<int> ret(N);
				ret[0] = m_ringSize[0];
				CDGTopSort topSort(neiBo);
				topSort.Init();
				for (auto it = topSort.m_vSort.rbegin(); it != topSort.m_vSort.rend(); ++it) {
					if (0 == ret[*it]) { continue; }
					for (const auto& child : neiBo[*it]) {
						ret[child] = max(ret[child], ret[*it] + m_ringSize[child]);
					}
				}
				return ret;
			}
			vector<int> m_ringSize;
		};
	public:
		int N;
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod11)
		{
			N = 7, edge = { {1,2},{3,1},{2,5},{2,4},{3,7},{3,5},{3,6},{6,5},{7,2},{4,7} };
			auto res = Solution().Ans(N, edge);
			AssertEx(6, res);
		}
		TEST_METHOD(TestMethod12)
		{
			N = 6, edge = { {1,2},{2,3},{3,1},{4,5},{5,6},{6,4},{5,3}};
			auto res = Solution().Ans(N, edge);
			AssertEx(6, res);
		}
		TEST_METHOD(TestMethod13)
		{
			N = 7, edge = { {1,2},{2,3},{3,4},{5,4} };
			auto res = Solution().Ans(N, edge);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod15)
		{
			N = 4, edge = { {1,2},{2,1},{3,4},{4,3},{3,1} };//不能去掉重边
			auto res = Solution().Ans(N, edge);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod16)
		{
			N =2, edge = { {1,2}};//不能去掉重边
			auto res = Solution().Ans(N, edge);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod17)
		{
			N = 3, edge = { {2,3} };//不能去掉重边
			auto res = Solution().Ans(N, edge);
			AssertEx(1, res);
		}
	};
	TEST_CLASS(P3436)
	{
		//【缩点 拓扑排序】P3436 [POI 2006] PRO-Professor Szu|省选-
		class Solution {
		public:
			pair<int, vector<int>> Ans(int N, vector<pair<int, int>>& edge) {
				N++;
				vector<int> ringSize, ptNew;
				vector<vector<int>> neiBo2;
				{
					for (auto& [u, v] : edge) {
						if (N == u) { u = 0; }
						if (N == v) { v = 0; }
					}
					sort(edge.begin(), edge.end());
					CSCCTarjanForwardStar scc(N, edge);
					ringSize.assign(scc.RegionCnt, 0);
					for (int i = 0; i < N; i++) {
						ringSize[scc.m_ptNew[i]]++;
					}
					neiBo2.resize(scc.RegionCnt);
					for (const auto& [u, v] : edge) {
						const int g1 = scc.m_ptNew[u];
						const int g2 = scc.m_ptNew[v];
						if (g1 == g2) { ringSize[g1]++; continue; }
						neiBo2[g1].emplace_back(g2);
					}
					ptNew.swap(scc.m_ptNew);
				}
				edge.clear();
				vector<int> vSort;
				{
					CDGTopSort topSort(neiBo2);
					topSort.Init();
					vSort.swap(topSort.m_vSort);
				}
				vector<int> ans(ringSize.size());
				ans[ptNew[0]] = 1;
				const int M = 36500;
				int iMax = 0;
				for (const auto& cur : vSort) {
					for (auto& chi : neiBo2[cur]) {
						ans[cur] += ans[chi];
					}
					ans[cur] = min(ans[cur], M + 1);
					if (ans[cur] && (ringSize[cur] > 1)) {
						ans[cur] = M + 1;
					}
					iMax = max(iMax, ans[cur]);
				}	
				vector<int> v;
				int preCnt = 0;
				for (int i = 1; i < N ; i++) {
					if (ans[ptNew[i]] == iMax) {
						v.emplace_back(i);
					}
				}
				return make_pair(iMax, v);
			}
		};

	public:
		int N;
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod11)
		{
			N = 3, edge = { {1,2},{1,3},{2,3},{3,4},{3,4} };
			auto res = Solution().Ans(N, edge);
			AssertEx(4, res.first);
			AssertV({ 1 }, res.second);
		}
		TEST_METHOD(TestMethod12)
		{
			N = 3, edge = { {3,3}, {3,4} };
			auto res = Solution().Ans(N, edge);
			AssertEx(36501, res.first);
			AssertV({ 3 }, res.second);
		}
		TEST_METHOD(TestMethod13)
		{
			N = 3, edge = { {1,2}, {2,1},{2,4} };
			auto res = Solution().Ans(N, edge);
			AssertEx(36501, res.first);
			AssertV({ 1,2 }, res.second);
		}
	};

	TEST_CLASS(P9220)
	{
		//【博弈 拓扑序 缩点】P9220 「TAOI-1」椎名真昼|省选-
		class Solution {
		public:
			string Ans(vector<int>& ws, vector<pair<int, int>>& edge) {
				const int N1 = ws.size();
				auto neiBo = CNeiBo::Two(N1, edge, true, 1);
				CSCCTarjan scc(neiBo);
				scc.InitPtNew();
				for (auto& v : scc.m_sccs) {
					for (int i = 1; i < v.size(); i++) {
						if (ws[v[0]] != ws[v[i]]) { return "N"; }
					}
				}
				auto nei = scc.GetNewNeiBo();
				if (2 == scc.m_v0.size()) {
					const int i1 = scc.m_v0.front(), i2 = scc.m_v0.back();
					const int tmp = ws[i1] + ws[i2];
					if ((2 == tmp) && (nei[i1].size() + nei[i2].size() == 0)) { return "B"; }
					if (1 == tmp)
					{
						if (2 == ws[i1] + nei[i1].size()) { return "B"; }
						if (2 == ws[i2] + nei[i2].size()) { return "B"; }
					}
				}
				CDGTopSort topSort(nei);
				topSort.Init();
				int root = -1;
				for (const auto& u : topSort.m_vSort) {
					if ((u != scc.m_ptNew[u])||(0==ws[u])){ continue; }
					root = u;
				}
				if(-1 == root) { return "B"; }//全白
				vector<int> vis(N1);
				vis[root] = true;
				for (const auto& u : vector<int>(topSort.m_vSort.rbegin(), topSort.m_vSort.rend())) {
					if (!vis[u]) { continue; }
					for (const auto& v : nei[u]) {
						vis[v] = true;
					}	
				}
				for (int i = 0; i < N1; i++) {
					vis[i] = vis[scc.m_ptNew[i]];
				}
				if (vis == ws) { return "A"; }
				return "N";
			}
		};
	public:
		vector<int> ws;
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod01)
		{
			ws = { 1 }, edge = {  };
			auto res = Solution().Ans(ws, edge);
			AssertEx("A", res.c_str());
		}
		TEST_METHOD(TestMethod02)
		{
			ws = { 0 }, edge = {  };
			auto res = Solution().Ans(ws, edge);
			AssertEx("B", res.c_str());
		}
		TEST_METHOD(TestMethod03)
		{
			ws = { 1,1 }, edge = {  };
			auto res = Solution().Ans(ws, edge);
			AssertEx("B", res.c_str());
		}
		TEST_METHOD(TestMethod04)
		{
			ws = { 1,1 }, edge = { {1,2} };
			auto res = Solution().Ans(ws, edge);
			AssertEx("A", res.c_str());
		}
		TEST_METHOD(TestMethod05)
		{
			ws = { 1,1 }, edge = { {2,1} };
			auto res = Solution().Ans(ws, edge);
			AssertEx("A", res.c_str());
		}
		TEST_METHOD(TestMethod06)
		{
			ws = { 0,0 }, edge = {  };
			auto res = Solution().Ans(ws, edge);
			AssertEx("B", res.c_str());
		}
		TEST_METHOD(TestMethod07)
		{
			ws = { 0,0 }, edge = { {1,2} };
			auto res = Solution().Ans(ws, edge);
			AssertEx("B", res.c_str());
		}
		TEST_METHOD(TestMethod08)
		{
			ws = { 0,0 }, edge = { {2,1} };
			auto res = Solution().Ans(ws, edge);
			AssertEx("B", res.c_str());
		}
		TEST_METHOD(TestMethod10)
		{
			ws = { 0,1 }, edge = {  };
			auto res = Solution().Ans(ws, edge);
			AssertEx("A", res.c_str());
		}
		TEST_METHOD(TestMethod11)
		{
			ws = { 0,1 }, edge = { {1,2} };
			auto res = Solution().Ans(ws, edge);
			AssertEx("A", res.c_str());
		}
		TEST_METHOD(TestMethod12)
		{
			ws = { 0,1 }, edge = { {2,1} };
			auto res = Solution().Ans(ws, edge);
			AssertEx("B", res.c_str());
		}
		TEST_METHOD(TestMethod13)
		{
			ws = { 1,0 }, edge = {  };
			auto res = Solution().Ans(ws, edge);
			AssertEx("A", res.c_str());
		}
		TEST_METHOD(TestMethod14)
		{
			ws = { 1,0 }, edge = { {1,2} };
			auto res = Solution().Ans(ws, edge);
			AssertEx("B", res.c_str());
		}
		TEST_METHOD(TestMethod15)
		{
			ws = { 1,0 }, edge = { {2,1} };
			auto res = Solution().Ans(ws, edge);
			AssertEx("A", res.c_str());
		}
		TEST_METHOD(TestMethod16)
		{
			ws = { 1,0,1 }, edge = { {1,2},{2,3} };
			auto res = Solution().Ans(ws, edge);
			AssertEx("N", res.c_str());
		}
		TEST_METHOD(TestMethod17)
		{
			ws = { 1,0 }, edge = { {1,2},{2,1} };
			auto res = Solution().Ans(ws, edge);
			AssertEx("N", res.c_str());
		}
		TEST_METHOD(TestMethod18)
		{
			ws = { 1,1,1,1,1 }, edge = { {1,2},{1,3} ,{2,4},{3,4} };
			auto res = Solution().Ans(ws, edge);
			AssertEx("N", res.c_str());
		}
	};
}
